Главная /
Рефераты / Выбор очередности обработки при двух агрегатах (алгоритм Джонсона)
Выбор очередности обработки при двух агрегатах (алгоритм Джонсона)
Общий случай задачи выбора последовательности обработки деталей на двух станках, если детали должны пройти обработку на одном станке, а затем на втором и на станке не может обрабатываться больше одной детали, рассмотрел в 1954 г. С. Джонсон. Метод решения такой задачи называют алгоритмом Джонсона.
Рассмотрим участок с двумя агрегатами. Совокупность деталей должна последовательно пройти обработку на первом агрегате, а потом на втором. Между агрегатами отсутствует склад, поэтому занятость второго агрегата задерживает освобождение первого. Требуется выбрать очередность обработки деталей, обеспечивающую меньшее суммарное время занятости участка. Это время рассчитывается от момента начала обработки первой детали на первом агрегате до окончания обработки последней детали на втором агрегате.
Очевидным является вывод, что выигрыша во времени можно достигнуть только за счет параллельной работы агрегатов. Длительная занятость первого агрегата, пока второй стоит, так же как и занятость второго, когда первый агрегат уже закончил работу, нерациональны. Отсюда ясно, что на первое место в очередности следует поставить деталь с меньшим временем обработки на первом агрегате. Аналогично на последнее место следует поставить деталь, у которой самое короткое время обработки на втором агрегате. Если это правило распространить на всю совокупность деталей, то получим алгоритм Джонсона.
Сначала выбираются детали, у которых время выполнения первой операции короче времени выполнения второй операции. Эти детали обрабатываются в порядке возрастания времени выполнения первой операции. Остальные детали обрабатываются в порядке убывания времени выполнения второй операции.
Условие оптимальной очередности пар деталей выглядит следующим образом:
min [a(i), b(i + 1)] < min [a(i + 1), b(i)].
Простой алгоритм решения задачи для двух станков вызвал многочисленные попытки обобщения полученного результата применительно к ситуации наличия нескольких станков. Однако все предпринятые попытки оказались успешными только в немногочисленных частных случаях. Общего алгоритма найти не удалось.
Большое распространение получили эвристические методы выбора последовательности обработки деталей, базирующиеся на правилах предпочтения. Выделим следующие используемые на практике правила предпочтения:
• раньше срок готовности на заключительной стадии технологического процесса;
• больше потери от пролеживания в незавершенном производстве;
• меньше запас времени по отношению к сроку готовности;
• деталь поступила на обработку первой;
• больший процент брака на последующих участках;
• меньше время обработки на первой стадии технологического процесса;
• больше время обработки на завершающей стадии технологического процесса.
Похожие рефераты:
